class Solution(object):
    def hannuota(self, k):
        lists = [str(i) for i in range(1, k+1)]
        return self.search_rode(lists, "A", "C")

    def search_rode(self, lists, location, direction):
        if len(lists) <= 1:
            return ["1:" + location + "-" + direction]
        mid_tar = ({"A", "B", "C"} - {location, direction}).pop()
        return self.search_rode(lists[:-1], location, mid_tar) + [lists[-1] + ":" + location + "-" + direction] + \
               self.search_rode(lists[:-1], mid_tar, direction)


a = Solution()
# print(a.hannuota(0))
print(a.hannuota(1))
print(a.hannuota(2))
print(a.hannuota(3))
print(a.hannuota(4))
